package list;

@SuppressWarnings("unchecked")
public class DynamicArray<E> {

	private int size;

	private E[] elements;

	private static final int DEFAULT_Capacity = 8;

	public DynamicArray(int capa) {
		capa = capa < DEFAULT_Capacity ? DEFAULT_Capacity : capa;
		elements = (E[]) new Object[capa];
	}

	public DynamicArray() {
		this(DEFAULT_Capacity);
	}

	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	/**
	 * 元素的数量
	 * 
	 * @return
	 */
	public int size() {

		return size;
	}

	/**
	 * 是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * 
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		for (int i = 0; i < size; i++) {
			if (elements[i] == element) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 添加元素到尾部
	 * 
	 * @param element
	 */
	public void add(E element) {
		this.ensureCapacity(size + 1);
		elements[size] = element;
		size++;
	}

	/**
	 * 获取index位置的元素
	 * 
	 * @param index
	 * @return
	 */
	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		} else {
			return elements[index];
		}

	}

	/**
	 * 设置index位置的元素
	 * 
	 * @param index
	 * @param element
	 * @return 原来的元素ֵ
	 */
	public E set(int index, E element) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		} else {
			E retInt = elements[index];
			elements[index] = element;
			return retInt;
		}
	}

	/**
	 * 在index位置插入一个元素
	 * 
	 * @param index
	 * @param element
	 */
	public void insert(int index, E element) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException();
		} else {
			for (int i = size; i > index; i--) {
				elements[i] = elements[i - 1];
			}
			elements[index] = element;
			size++;
		}
	}

	/**
	 * 删除index位置的元素
	 * 
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		} else {

			E retInt = elements[index];
			for (int i = index; i < size; i++) {
				elements[i] = elements[i + 1];
			}
			size--;
			elements[size] = null;
			this.trim();
			return retInt;

		}

	}

	/**
	 * 查看元素的索引
	 * 
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null)
					return i;
			}
		}
		for (int i = 0; i < size; i++) {
			if (elements[i].equals(element)) {
				return i;
			}
		}
		return 0;
	}

	public String printStr() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				sb.append(",");
			}
			sb.append(elements[i]);
		}
		sb.append("\n");
		return sb.toString();
	}

	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity < capacity) {
			int newCapacity = oldCapacity + (oldCapacity >> 1);

			E[] newElements = (E[]) new Object[newCapacity];
			for (int i = 0; i < elements.length; i++) {
				newElements[i] = elements[i];
			}
			elements = newElements;
			System.out.print(oldCapacity + "======  kuorongwei:" + newCapacity + "\n");
		}
	}

	private void trim() {
		int oldCapacity = elements.length;
		int newCapacity = oldCapacity >> 1;
		if (size > (oldCapacity >> 1) || oldCapacity < DEFAULT_Capacity) {
			return;
		} else {
			E[] newElements = (E[]) new Object[newCapacity];
			for (int i = 0; i < size; i++) {
				newElements[i] = elements[i];
			}
			elements = newElements;
			System.out.print(oldCapacity + "=====  kuorongwei:" + newCapacity + "\n");
		}

	}

}
